/**
 * 116. 填充每个节点的下一个右侧节点指针
 * https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
 */
public class Solutions_116 {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);  // output: {1, #, 2, 3, #, 4, 5, 6, 7, #}

        Node result = connect(root);
        System.out.println(result);
    }

    /**
     * 完美二叉树：所有叶子节点都在同一层，每个父节点都有两个子节点。
     */
    public static Node connect(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            // 为左子节点获取 next
            root.left.next = root.right;
        }
        if (root.right != null) {
            // 为右子节点获取 next（否则默认为 null）
            if (root.next != null) {
                // 右子节点的 next 只能是父节点的 next 的左子节点
                root.right.next = root.next.left;
            }
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
}


